package everydayone.sortArray;
/**
 * @Date 2020/04/1
 * @author 王光浩
 * @Thinking 堆排序
 */
public class MyMethodFour {
	public int[] sortArray(int[] nums) {
		int len=nums.length;
		heapify(nums);  //将nums数组初始化为一个大值堆
		for(int i=len-1;i>=1;) {
			//将堆顶（最大值和队尾元素进行交换）
			nums[i]=nums[0]^nums[i];
			nums[0]=nums[0]^nums[i];
			nums[i]=nums[0]^nums[i];
			i--;
			//将堆尾元素
			siftDown(nums,0,i); //将堆顶元素下沉，这样堆的最大元素就会浮上来
		}
		return nums;
	}
	//初始化堆（大值堆）
	private void heapify(int[] nums) {
		int len=nums.length;
		for( int i=(len-1)/2; i>=0; i--) siftDown(nums,i,len-1);
	}
	/**
	 * @param nums 原数组
	 * @param k    当前下沉元素的下标 
	 * @param end  [0,end]是nums的有效部分
	 */
	private void siftDown( int[] nums, int k, int end) {
		while (2*k+1<=end) {   //当当前节点没有左右子树时，则退下沉结束
			int j=2*k+1; //获取k的左子树
			if( j+1<=end && nums[j+1]>nums[j] ) j++; //如果右节点的值比左节点的值大，则将j++
			if( nums[j]>nums[k] ) {    //如果当前节点值小于子节点值，则进行交换
				nums[j]= nums[j]^nums[k];
				nums[k]= nums[j]^nums[k];
				nums[j]= nums[j]^nums[k];
			}
			else break; //如果当前节点比左右子节点值都大，则结束下沉
			k=j;
		}
	}
}
